/*
首先能够四个方向走，因此直接从00开始即可。同时即使某个点符合特殊条件如果周围四个点都是0那这个点也走不到，所以还是不能遍历。
*/

class Solution {
public:
    int Sumofg(int num)
    {
        int re=0;
        while(num>0)
        {
            re+=num-(num/10)*10;
            num/=10;
        }
        return re;
    }
    void move(int** &mat,int i,int j,int&k,int&m,int&n)
    {
        if(Sumofg(i)+Sumofg(j)<k+1&&mat[i][j]==0)
        {
            mat[i][j]=1;
            if(i-1>=0)
            {
                move(mat,i-1,j,k,m,n);
            }
                        if(i+1<m)
            {
                move(mat,i+1,j,k,m,n);
            }
                        if(j-1>=0)
            {
                move(mat,i,j-1,k,m,n);
            }
                        if(j+1<n)
            {
                move(mat,i,j+1,k,m,n);
            }
        }
    }
    int movingCount(int m, int n, int k) 
    {
        int re=0;
        int**mat=new int*[m];
        for(int i=0;i<m;i++)
        {
            mat[i]=new int[n];
        }
        //矩阵初始化
        
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                mat[i][j]=0;

            }
        }
                
        
            
            
                
                
        move(mat,0,0,k,m,n);
                

            
        
                for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if (mat[i][j]==1){re++;}
            }
        }
        return re;
    }
};